package Sort_06;

/*
 * @Author 罗
 * @date 2020/3/16 - 9:59 上午
 *
 */

import java.util.Arrays;

public class Bubble_Sort_02 {


    /**
     * 冒泡排序
     * 使用了双层嵌套for循环，时间复杂度为O(n^2)
     *
     * @param array
     */
    public static void bubbleSort(int[] array) {

        int temp;
//        标识，表示本趟排序是否进行了交换
        boolean haveFinished = true;
        /*   一共进行(数组.length - 1)次大的循环，
                只为找出(length - 1)的大的数字并且排到后面，
                还剩一次，因为最后那个数是最小的数字，没有必要排序

         */
        for (int j = 0; j < array.length - 1; j++) {
            /*
             * 每一趟排序的次数在减少，因为每经过一趟排序，
             * 就能排出一个最大值并放到后面
             * 之后每一趟排序出的较大数都不会比之前趟排序出的结果更大
             *
             * 每一趟排序都将本趟排序的最大值放在后面
             * */
            for (int i = 0; i < array.length - j - 1; i++) {

                if (array[i] > array[i + 1]) {
                    temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    haveFinished = false;
                }
            }
//            System.out.print("第"+j+"趟排序，就是把第"+j+"趟的最大值"+array[array.length-1-j]+"放到"+(array.length-j)+"(倒数第"+(j+1)+")位置");
//            System.out.println("\t结果"+Arrays.toString(array));
            /*
             * 如果某一趟排序中没有进行任何交换，则可以提前结束排序
             * */
            if (haveFinished) {
                System.out.println("提前跳出");
                break;
            }
//            重制标志位，进行下一次判断
            haveFinished = true;

        }
    }
}
